package MonotoneStack.Hard;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

public class LC0084 {
    /**
     * 思路：考虑以每个元素e（e为索引）的高度作为矩形的高度，矩形最大能达到多大的面积，记这最大面积为f(e)。
     * 容易证明，这样找到的矩形最大值max{f(e)}一定是最优解。
     * 使用单调栈找这样的最大值。对于每个元素e，循环出栈每个大于e的栈顶元素t，并计算f(t)；如果遇到高度不大于e的栈顶元素，将e入栈。
     * 计算f(t)的方法为：先将t出栈，假设新的栈顶元素为t'，待入栈元素为e，那么f(t)=heights[t]*(e-t'+1)。
     * f(t)计算方法的核心在于，可以证明[t'+1,e-1]范围内，t的高度一定不大于任何其他的元素，保证f(t)符合我们最初的定义。
     * 【这也是用这种方法构造单调栈时的重要性质。】
     * 边界处理：可以再heights前后都增加一个高度为-1的虚假元素（其实就是哨兵）。
     * 时间复杂度：N。
     */
    public static int largestRectangleArea(int[] heightsAsArray) {
        int n = heightsAsArray.length;
        ArrayList<Integer> heights = new ArrayList<>(n + 2);
        heights.add(-1);
        for (int e : heightsAsArray) heights.add(e);
        heights.add(-1);

        Stack<Integer> monoStack = new Stack<>(); // 栈中存储索引
        monoStack.add(0);
        int maxArea = -1;
        for (int e = 1; e < n + 2; e++) {
            while (heights.get(monoStack.peek()) > heights.get(e)) { // 栈顶元素大于待入栈元素，将栈顶元素出栈并计算f(t)
                int h = heights.get(monoStack.pop());
                int w = e - monoStack.peek() - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            if (heights.get(monoStack.peek()) < heights.get(e)) { // if和else的操作是一样的，为了清晰性没有合在一起
                monoStack.push(e);
            } else { // 栈顶元素高度和e相同
                monoStack.push(e); // 如果e不是哨兵，正常入栈；如果e是哨兵，不会有下一次循环，对结果无影响
            }
        }

        return maxArea;
    }

    /**
     * 这个版本省去了重新构造List的过程，并且省去了入栈时的if，从而节省时间，其他相比基础版本没有变化。
     * 运行时间相比基础版本没有明显提升。
     */
    public static int largestRectangleArea2(int[] heights) {
        int n = heights.length;

        Stack<Integer> monoStack = new Stack<>(); // 栈中存储索引
        int maxArea = -1;
        for (int e = 0; e < n; e++) {
            while (!monoStack.isEmpty() && heights[monoStack.peek()] > heights[e]) { // 栈顶元素大于待入栈元素，将栈顶元素出栈并计算f(t)
                int h = heights[monoStack.pop()];
                int left = !monoStack.isEmpty() ? monoStack.peek() : -1;
                int w = e - left - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            monoStack.push(e); // 栈为空，或栈顶元素小于等于待入栈元素e，均可直接入栈
        }
        // heights遍历完成，处理栈中剩余元素
        int right = n;
        while (!monoStack.isEmpty()) {
            int h = heights[monoStack.pop()];
            int left = !monoStack.isEmpty() ? monoStack.peek() : -1;
            int w = right - left - 1;
            maxArea = Math.max(maxArea, h * w);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = new int[]{0, 1, 0, 1};
        System.out.println(largestRectangleArea(heights));
    }
}
